"LI E> HAHY OF THE UNIVERSITY OF ILLINOIS 510.84 I26T no. 156-163 cop 2 Digitized by the Internet Archive in 2013 http://archive.org/details/generaltheoryofm163koma fC\ S4- DIGITAL COMJ'U'PKK LABORATORY ^ ^ "*" UNIVERSITY OF ILLINOIS ^p ^ URBANA, ILLINOIS REPORT NO. 163 GENERAL THEORY OF MOST EFFICIENT CODES by Yasuo Komamiya June 9, 196^ The person charging this material is re- sponsible for its return on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. University of Illinois Library ACKNOWLEDGMENT The author wishes to thank Professor David E. Muller for a number of helpful discussions in connection with this report, and Mrs. Phyllis Olson for her skillful typing of this paper. TABLE OF CONTENTS Page 1. INTRODUCTION 2. A THEOREM WHICH PLAYS AN IMPORTANT ROLE IN THE CODING PROBLEM . . 3 3. GENERAL THEORY OF MOST EFFICIENT CODES L3 k. CALCULATION AND SOME PROPERTIES OF EACH \ 28 l 5. SOME PROPERTIES OF C, 37 6. SOME PROPERTIES OF Z (CF. DEFINITION 3.6) 51 7. SOLUTION OF EQ. (3-25) "VA'V T = 0" UNDER CONDITION 6.1 AND CONDITION 6.2 70 8. GENERAL SOLUTION OF VA' V T = 91 9. GENERAL SOLUTION OF VA' V T = IN APPLICATION OF BOOLEAN ALGEBRA . 101 10. CONCLUSION . 106 •in- 1 . I NTKODUCTION In this paper, the number of most efficient binary codes and the construction methods are discussed in general, where the most efficient binaj codes mean codes with a minimum Hamming distance of p. The most efficient binary codes are defined mathematically as follows M(n,p) = 11, X 12' x 13' x^. , x L ln x 21 , x 22 , x 23 , ..., x 2n , x. 31' 32' 33' "" 3n (1.1) X -i » X„, X _, • . • , X , ml m2 m3 mn. Consider the matrix M(n,p), where (x.,iX.„,...,x. ) for 1 < i < m ll i2 in — — is an n digit binary code. Accordingly, x. . is 1 or and m is the number of ■^- J most efficient binary codes. Here x., - x . , + x . ^ - x . ^ + . . . + x. -x. >p for any i f j; 1 < i, j < ll jl 1 ' i2 j2' ' in jn 1 - ^ J r d ' - ' J - m where p is the minimum Hamming distance. The purpose of this paper is to obtain maximum m and the value of each x. . . ij In Section 2, a theorem which plays an important role in the coding problem is discussed. In Section 3> the matrix H(n, p) (by which the coding problem can be discussed in general) is introduced, and general theory discussed. As a result, the coding problem is reduced to the problem of determining the independence of some vectors. In Section k, the characteristic values of H(n,p) are discussed. In Sections 5 and 6, some properties of the independence of vectors are discussed. In Section 7> solution under some conditions (group code condition implies these conditions; accordingly, group code is a special case of these conditions) is discussed. In Section 8, one method of general solution is discussed. In Section 9> Boolean algebra is used in finding a general solution, The c onclusion is stated in Section 10. 2. A THEOREM WHICH PLAY J AN IMPORTANT ROLE IN THE CODJN') PROBL In this section a theorem which piays an important role in the coding problem is first described, followed by a discussion of a second, related theorem. Definition 2.1 . Exclusive-OR operation "©" between any non-negative integers. Let a, b be non-negative integers. Define a © b as follows: when a and b are expanded to binary form, i.e., a = a2 + a .,2 + . . . + a, 2 + a_ n n-1 1 b = b 2 n + b ,2 n_1 + ... + b-,2 + b_ , n n-1 1 n-1 a © b = (a © b )2 + (a , © b , )2 + . . . + (a, © b, )2 + (a_ © b,J . n n n-1 n-1 1 1 Here the symbol "©" of the right-hand side of the above formula is an exclusive- or operation in the usual meaning. Theorem 2.1. Let z~, z. , .... z , be real numbers. Consider the matrix 7 1 n-1 Z = n V V V ■"" Z N-1 'l' V z 3' '"' z l©(N-l) 'i> Z i©l' Z i©2' '"' Z i©(N-l) Z N-1' Z N-2' Z N-3' ""' Z where N = 2 and n > 1, -k- The matrix Z can be transformed to the diagonal matrix by the orthogonal matrix as follows where Z = U AU n n n 1, 1 Un V N \l, -I* '1, 1 l1, "I, X . . . X '1, 1' a, -i- - (u ,u i; •••* u (n_ 1 )-) and A = : (N-1), Here, the symbol "x" means the direct product (Kronecker's product) and i, i\ A, i i, i k i, -I. X \ I X ... X ^1, -1/ \h -1 '1. 1 means the n direct products of The following relations can also be obtained 1, "I x. = -A (vV-"' z (n-i) )u i z i ■ ^ (x O' X l'"" X (N-l) )u i for any i, where < i < (N - 1). -5- Proof. Since the matrix Z is a symmetric real matrix, Z can be transformed n n to a diagonal matrix by an orthogonal matrix. When n ■ 1, Z, , U, are z - ■ V Zl V z o u ^vtC-J = (u °' Ul) respectively. The relation u ( X ° ° ) u = -± ( lr ) ( X ° ° ) -i I 1 ' ) = i f X ° + Xl ' X ° ' Xl 1 \0 x 1 / X ^2 \1, -1/ \0 x 1 /^2 \1, -1/ 2 \x - x x , x Q + Xl holds. Therefore, letting z Q = | (x Q + xj_) = \ (x Q ,x 1 ) f j = j (x ,x 1 )u z i = I (x o - x i } = \ ( V x i } (J = ^ ( V x i )u i' the relations x Q = z Q + z ± = (z , Zl ) ( ^ j = nT 2 (z , Zl )u x i = z o - z i = ( V z i } (^J = ^ ( V z i )u i can he obtained. Therefore, the theorem holds for n = 1. Now suppose that xhe theorem holds for n, then it may be proved by mathematical induction that the theorem also holds for (n + l). It is possible to let -6- n+l x , x 1 X l' x o where and X = Z n X l = V Z N+1' "••' Z 2N-1 . N+1 , z N , . .., z le ( 2N _-L) J N+2' (2.1) The relation Z 2N-1' Z 2N-2' '"' Z N n+1 1, 1 J 2 (n+1) \ 1, -1 I X . 1, -1 (n + 1) . X 1, 1 1, "I _1 sT 2 1 1. 1 U/^ \l, -1 V 1, 1\ /I, 1 x...*[ n X 1, "I .1, -1, _> 1, 1> ^2 ^ X \l, -1, , /U , U 1 / n n ^2 U , -U n n (2.2) holds clearly. As the theorem holds for n from the assumption, -7- x n = u n \ N-l y. =A (z ,z 1 ,...,z N _ 1 )u. 1 'N r '^o ,J l' ••*"N-1 / '*I > (2.3) hold, where < i < (N - l). In Eq. (2.1), letting z . _ = z i©N i for < i < (N - 1), X n = '1* z l> z 0' > Z N-1 Z N-1' Z N-2' "•' Z 1©(N-1) ., K holds. Therefore applying the theorem to X, , X = U 1 n y N+l U >v y 2N-l' y (2A) y n©i =</n ^i' z I"-- Z N-l )u i =VN ( VVl-' Z lH )u i 1 Z n©i ~ ^ (y r y N+l^°^ y 2N-l )u i ^ hold. Now, let -8- A, = > X (N-1) > (2.5) 'N ^N+l A. x 2N-1 7 J such that ^ I < A 1 + V = N-l > N N+l | (A,-A 2 ) (2.6) y 2N-l' Then from Eqs. (2.1) through (2.6), the relation -9- Un+1 \o a) Un+i , u u / n n U -U n n A i ° *2 u , u n n U , -U n n A l +A 2 u — u , u A, ■ Ag U n 2 n n 2 n \~*2 A l +A 2 u , u — u n 2 n n 2 n X Q , X-j^ x x , x Q = z (n+1) holds. Therefore, A l ° (n+l) n+1 \ Q / n+1 n+ x Vi < 2 - 7 » x (2N-1), holds . From Eqs. (2.5) and (2.6), X i = y i + y N+l X N+1 == y i ~ y N+l hold, where < i < (N - 1). Therefore, from Eqs. (2.3) and (2.4), = n/n (V z l— Vl^i WN ( V Z N+l--- Z 2N-l )u i N ^ V z i>--> z N-r V z n+i' • • • ' z 2n-i ■ u. (2.8) ■10- *N+i =/N ( W--- Z N-1 )U 1 -^ ( V Z N + l'-"' Z 2N-l )u i (u. 1 -u. (2.9) can be obtained, where < i < (N - l). Letting U . = (v , v,, . . . , V 2N _]_)^ N+l v. = l - r 1 ^2 \ u. > 1 f U i N+l J"s •u. (2.10) holds, since i / U » U u i ="F n n n+1 ^2 V U , -U x n n /here < i < (N - l). Therefore, from Eqs. (2.8), (2.9), and (2.10), x x. =n/2N (z ,z 1 ,...,z 2N _ 1 )y. "\ } z ] v 2N-1 ; N+i (2.11) can be obtained where < i < (N - l). From Eq. (2.11), the relation (W-'W =nS> ( W"-' z 2n-i )( V v i"-" v 2n-i ) = ^ (VV-' Z 2N-l )U n + l holds. Therefore the relation ■ 11- ( V Z 1--- Z 2N-1 ) = ^ ( V X r-'Vl )U r 1+ l v2N holds since U n U , = E , • where E . is the unit matrix of order n+1. n+1 n+1 n+1 n+1 From Eq. (2.12), Z i ^ ( V X l^*^ X 2N-l )v i can be obtained, where < i < (2N - l). The above description has made it clear that the theorem holds for (n + 1). Theorem 2.2. In Theorem 2.1, T„ T u.Z = x.u. in li n T holds, where < i < (2 - l), and u. means the transposed matrix of u. Proof . From Theorem 2.1, x x u x l u T Z = u T U . |U = (0,... ,0,1,0,. ..,0) I . JU in\ . In I , /n / \ ° ' X N-l/ \ X N-1> = (0, . . .,0,x.,0, . . . ,0)U = (x.u. _, x.u. ,,..., x.u. , v ) ' ' ' i' ' 7 ' n l lO i ll l i(N-l) T x. (u.-.,u. ,, . , .,U. /„ ,\) = x.u. i lO ll i(N-l) l l can be obtained, since ■12- T U n = (u ,u r ..., Vl ) = l N-l 3. GENERAL THEORY OF MOST EFFICIENT CODES Definition 3-^- » 1 code Let i be a positive integer, ^ i < (2 - l), and let the binary expression of i be as follows: i = x. / x2 + ... + x.,2 + x._. i(n-l) ll iO The n, let the binary code (x. , 1 u...,x.,iX Jft ) be called "i" c i(n-l; ll iO ode Notation 3-1 . dist(i,j) Let the Hamming distance between i code and j code be expressed by dist(i, j). From Definition 2.1, Definition 3«1 and Notation 3«1.> dist(i, j) = i e j (3.1) clearly holds Definition 3.2. Matrix H(n, p) The matrix H(n, p) is a square matrix of order 2 and is defined as follows : 00' h 0l' h 02' > h 0(N-1) H(n,p) h 10' h ir h 12' ■•■' h l(N-l) h 20 , h 21 , h 22 , ..., h 2(N _ l} h (N-l)0' h (N-l)l' h (N-l)2, *' h (N-l)(N-l) / (3.2) -13- -1k- where N = 2 , n > p > 1. Here, h . = 1 when dist(i,j) < p h. . = when dist(i.j) > p ij - > From Notation 3»1> dist(i,j) = i©j=Oe(iej) = dist(0, i e j) holds. Therefore, (3.3) h . . = hu. / . . \ ij 0(i©j) (3A) can be obtained. Now, define h. as follows 7 l h. = h n . l Oi (3-5) Then, h n = h. . li 1 i,i©l lu = h. i,i« = h i©l,i h. 1©2,1 (3.6) ^-1 " h i,ie(N-l) h ie(N-l),i can be obtained for any i (0 < i < N - l). Therefore, the matrix H(n,p) defined by Definition 3.2 can be expressed by ■15- H(N,p) = h Q , h L , h 2 , h> V h y ...,h le(N-l) V h iel' h ie2' ••" h ^ ie(N-l) (3-7) .V-l' \-2' ^-3' '■'> .., K where h = h. . = 1 li (3-8) From Definition 3.2 and Eq. (3»6)> h o + h i + •'• + \-i = h io + h u + ••• + h i (N-l) = K(n,p) (3-9) can be obtained, where K(n,p) = C„ + C-. + ... + C v ,r n n 1 n p-1 (3.10) Example 3 » 1 H(n,l) = = E. K(n,l) = n C = 1 Clearly, H(n, l) is a unit matrix of order N. Example 3*2 Example 3 • 3 H(n,n) = ■16- K(n,n) = CL + O. + CL + . . . + C _ = 2 n - 1 n n 1 n 2 n n-1 H(3,2) = K(3,2) = 3 C Q + C^ = 1 + 3 = k Theorem 3-1 - The matrix H(n, p) can be transformed to a diagonal matrix by the orthogonal matrix U , that is, n' ' H(n,p) = UAU ' n n and \ =Vn (VV-ViK hold, where -17- h i = ^ ( VV-Vi )u i A = \ ° N-l Proof . Applying Theorem 2.1 to H(n, p), the theorem clearly holds. Now, the most efficient coding condition is equivalent to the following condition: that is, to find a maximum m such that H = E m (3.11) where H o = ih~, h. . , h. ...... h. i,©i ' i-.©i ' i,©i 12 13 1 m h i 2 ®V V h. .,..., h. . i_©i ' 1 ®i 2 3 2 m h. . , h. . , h^, . . . , h. 3 13 2 3 m (3-12) h . . , h . . , h . ...... h_ 1 ©l-,' 1 ©1 ' 1 ©1 ' ' ml m 2 m 3 and E is the unit matrix of order m. m Therefore, from Theorem 3-l> "the most efficient coding condition is also equivalent to the following condition: that is, there exist u. , u. , X l X 2 u. for maximum m such that 1 m -18- H = U T u. A(u. ,u. , . . . ,u. ) = E 1, 1 ' 1 m 12 m (3-13) in) where u U n = (u 0)Ul ,...,u H ) = \u N-li that is, u., etc., means the transposed matrix of u., etc, Now, let V = (3.14) Then, Eq. (3-13) leads to m/ T VAV = E for maximum m. m (3.15) Asu. , u. , ..., u. are column vectors belonging to the orthogonal matrix U , 1 1 1 2 1 m T W = E m (3.16) -19- can be obtained. Therefore, from Eqs. (3«i5) and (3.16), T T VAV = VV = tn .*. V(A - E N )V T = (3.17) can be obtained, where E is a unit matrix of order N and the right-hand side "0" of (3»17) means the zero matrix of order m (where every element is zero). Definition 3-3 » Define the vectors £„, C,, , ..., i , as follows V T u. ' r„ ^o ;5 l"" ,& N-l^ >/n ml There exist m independent vectors among i , £ , ..., L since V consists of m row vectors belonging to the orthogonal matrix U . Therefore, as understood clearly from Eq. (3. 17) and Definition 3°3> the most efficient coding condition may be found by finding the solution of the following equation: (£ ,5 1 ,...,.£ b . 1 )(a - V«o' c i'-"'Vi ) = ° (3 - l8) such that the number of the independent vectors among ( £ n , £, , . . . , C ) becomes as large as possible. -20- Now, some relations which hold among i , £ , . .., C are described below. Definition ?>.k . Operation s Given two matrices A and B whose number of rows and columns are n and m respectively, i.e. ' a ll' a l2' "*' a im' a 21 , a 22 , . .., a 2m A = and B = b lx , b 12 , ..., b lm b 21 , b 22 , ..., b 2m a,, a , . . . , a nl n2 nm/ b .., b _, ...fti nl n2 nm Define A a B as follows ' a ll b ll> a 12 b 12' "■'' a T- b ^l^l' a 22 b 22' '"'' a ° mlD A b B a , b , , a _b _, . . . , a b nl nl' n2 n2 nm nm, Definition 3.5. |. Define | . as follows 1 Vn U = (l ,^ •'^N-l^ that is, l , |,, . .., I N are the column vectors of vN U . Accordingly, I . = VN u . (3.19) holds . -21- Theorem 3-2 6 t«i = e t ■ h holds, for any t, i (0 < t, I < N - l) Proof. When n = 2, n u, -1, x 1, 1 1, -1 1, 1, 1, 1 1, -1, 1, -1 1, 1, -1, -1 1, -l, -1, 1 0' 1' P' v holds. Therefore f 3- can he obtained. Therefore, the theorem holds for n = 2. Assume that the theorem holds for n. Then, by mathematical induction, the theorem also holds in the case (n + l). 7 2 (n + l) y m J^ [ ^ 2 n U, ^2 n U n n n+1 1, -1 sf^U , -^ (3.20) u n, holds, clearly. Since the theorem holds for v2 U by the assumption, the theorem clearly holds for r -22- Therefore, letting \l2^ n+1 ' U , be expressed by ^^ ' U n + 1 = (VV-VrV-W^ (3.21) the theorem holds for 2% n ) = 'VV-'Vi 1 n. (3-22) Since and ^u n = (i^,...,!^) J^ V2 n U. , N/2 n U U n+1 \ . O? ^2 n U , W2 n U * n r (3.23) i-l holds. Therefore, ■:']- W -5 1 -1 ■1 = \» m \ m1 *i , -1 holds where < I < N - 1. The above discussion has shown that the theorem holds for (n + l) Theorem 3-3 ^ = c t H H holds, for any t, I (0 < t, Z < N - l). Proof. The result is clear from Theorem 3.2 and Definition 3-3< Definition 3«6- z. Define z n , z, , z , . .., z , as follows: •4 z, = (1,1,...,1)L, that is, z. is ~r- multiplied by the sum of all elements of the vectors £ 1 n/n Theorem 3»^ C t ' ; I ■ /H z tel for any t, I (0 < t, i < N - l) . ■2k- Proof . #i = (1,1,. ...,!)(£ a (,«) = (1,1,...,1)L S (from Theorem 3.1) '£ f£ - z te£ (from Definition 3.5) From Definition 3-3 and Theorem 3«^> T 1 V V = - N .T 5 N-1 (^ ^ 1 ,...^ N _ 1 ) - N C T C C T C C T C C T C b CTO' b b l' b S 2' '"' b O b N-l C T C C T C C T C C T C \ C T c C T c C T c C T c \ b N-lV b N-l b l' b N-l' b 2' *' b N-l b N-l ( _1 nTn rz , z x , z 2 , -i /T\T * -1 ' Z N-1 J l' V Z 3' "•' Z 1©(N-1) i' xel' ie2' "' i©(N-l) (3-21+) lZ N-l' Z N-2' Z W-3' "*' Z can he obtained . Now, following the preliminary discussion above, the most efficient coding condition is discussed below. Definition 3«6. Define A' ,\! as follows -25- /V 1 A' = A - E N = V 1 \ /* •(N-l) 4 / - 1 ' \ S-i/ (cf. Theorem 3.1) Definition 3.7. Z Define Z as follows = n/n V V = '1' 2' z l> V V Z V 'V ' Z N-1 ••"' Z 1©(N-1) •"> Z 2©(N-1) Z N-1' Z N-2' Z N-3' °°°' Z From Eq„ (3«17) and Definition 3-6, VA'V T = (3o25) can be obtained. Therefore (V T V)A'(V T V) = (3.26) can be obtained. Conversely, from (3.26) and (3.16) V(V T V)A*(V T V)V T = VA'V T = can be obtained. Therefore, when W = E holds, the condition (3«25) is m equivalent to the condition (3.26) -26- From Eq. (3-26) and Definition 3.6, ZA'Z = (3-27) can be obtained. Therefore, to find the most efficient coding condition, find the maximum m such that W 1 = E > ZA'Z = (3.28) T T Theorem 3.5 . When VV = E and V V = Z, the rank of Z is m and the characteristic values of Z consist of "l" (m times) and "0" (N - m times). Proof. Since W = E holds, m ' det(\E - VV T ) = (X - l) m m can clearly be obtained. On the other hand, since holds generally, T T N-m det(\E„ - V V) = {det(\E - W )}X N m det(\E N - V T V) = (\ - l)^ (N - m) (3.29) can be obtained. T, Applying Theorem 2.1 to V V, / °' Z = n/n V V = z . , z. -27- z l' ••" Z N-1 ., ^ iel , ..., - ie(N _ 1 ) Z N-1' Z N-2' •**' Z = U U x (N-l) (3-30) can be obtained. From Eqs. (3.29) and (3«30)> "the rank of Z is m and the characteristic values of Z, i.e., x„, x, , ..., x w _ 1 consist of "l" (m times) and "0" (N - m times) . k N-l From Theorem 3-5> finding the condition for the most efficient codes can also be reduced to finding the solution of equations T W = E m ZA'Z = J (3.31) with the maximum rank of Z. Remark 3.1. From (3. 30), -A (w- z N-i )u i can be obtained. If x. = x. = ... = x. =1 and the other x. = 0, i_, code, L, 1_ 1 1 1 12 m i,. code, ..., i code are all of the most efficient codes. 2 m h. CALCULATION AND SOME PROPERTIES OF EACH \. The value of each X. is given by the formula of Theorem 3-l> i.e., X. =nT N (h ,h 1 ,...,h N _ 1 )u. where each h. is decided uniquely by the value of n and p. Another method of calculating each X. and some properties of X. are discussed below. Theorem 4.1. p = 1 if and only if \„ = A., = ... = X„ , = 1, ^ J 1 N-l Proof . If X = X = N , = 1, from Theorem 3«1* h i = ^ ( VV--ViK "z (1 ' 1 '-" 1)u i = Vn 1 when i = when i / can be obtained. Therefore, H(n,p) = can be obtained. Therefore, p = 1. Conversely, if p = 1, h~ = 1, h. = for i / l ' can be obtained. Therefore, /. . = "/n (1,0,0, . ..,0)u. = 1 for any i (0 < i < N - l) Therefore, the theorem holds. -28- -29- Theorem 4.2 \ Q + ^ + . . . + X N _ X = N ^2 .2 x + \ x + + \ N _ ] _ = NK(n,p) Proof. From Theorem 3.1* + \ 1+ ... + X N-1 =Vu (h ,h r ...,h N _ 1 )(u + u 1+ ... + Vl ) = ^N (VV— 'W nTn = Nh = N can be obtained. From Theorem 3-l> H(n,p) = U AU ' n n 2 2 H = U AU n n X\ =^N (^^...^^^u. can be obtained, where ho \ H(n,p) s (^J^,...,^) = T T S-l Therefore, ■30- ,2 .2 X + \ + + Sli =n/n ^oVfe-fei^o + u i + ••• + Vi } = ^n (rg£ £^,. T Vn-i^ n/n = N£ J!, = N(h Q + 1^ + ... + hjj^) = NK(n,p) Theorem ^-.3 . The following relations hold: (1) \ Q = K(n,p) (2) Any \ for 1 < i < N - 1 are \ = K(n,p) > X = integer where the equality holds if and only if p = 1 Proof. From Theorem 3«1; \ ± = VN (hQ,^, ...,h N _ 1 )u i = (h^h^ .. •^ h N _ 1 )i i = integer can be obtained, Since each h. is equal to 1 or 0, (h ,h 1 ,.„.,h N _ 1 )u > (h ,h 1 ,...,h N _ 1 )u. and \ = A (h ,h 1 ,...,h N _ 1 )u = h Q + 1^ + ... + hjj^ = K(n,p) -31- .*. K Q m K (n,p) > \. can be obtained. Suppose that there exists i, 1 <. i < (N - l), such that Then, x . v can be obtained, Since (V h l'---' h N-l )u O = 'Vl'-'Vl'"! (h ,h 1 ,...,h N _ 1 )(l - 5 .) =0 n d - e ± ) - \ i i + 1 + 1 + 1 each element of (I - |.) is equal to 2 or 0, i.e., non-negative, and there exist elements except the first row element such that the value is equal to 2, (Clearly, there is no case except p = 1 for n = 1.) Therefore, (h ,h 1 ,...,h N _ 1 )(i - |.) = holds if and only if h =1, h, = h = p = 1. V: 0. This is the case where -32- Theorem k.k where where X = X = ... = X 12 n X = X =.....= X r +r r i +r o r i +r 12 13 n-1 n X = \ = ... = X r, +r +r_ r, +r_+r, r ^+r , +r 12 3 12 4 n-2 n-1 n X = X = ... = X r, +r +...+r . r,+r_+...+r +r r^+r.+.^+r 1 2 n-1 1 2 n-2 n 2 3 n Q n-1 n-2 o r 1 = 2 , r 2 = 2 , . . . , r n = 2 = 1 , Proof. Consider any permutation of the correspondence X i(n-1)' X i(n-2)' ■•" x il' X i0 >-. ^ X , jf . . ■ <, X . ^ x . 1S (n-l) 1S (n-2) 1S 1 1S 1 = x. / ,\2 + x. / „x2 + . . . + x.,2 + x. n i(n-l) i(n-2J il i0 that is, any change of the column position of codes. From the definition of H(n,p), i.e., Definition 3-2, H(n,p) is invariant under this change. In H(n,p) = U AU , U is also invariant under this change. ' n n' n Suppose that A becomes V under this change. Then, H(n,p) = U AU = U ^U 7 n n n n holds. Therefore, -33- A = V can be obtained. Therefore, A has to be also invariant under this change As mentioned above, \ = X = . . . = \ 12 n \ = \ = ... = \ r,+r_ r-,+r_ r , +r 12 13 n-1 n \ = X = ... = \ r,+r^+ ..+r . r,+...+r +r r.+r,+...+r 1 2 n-1 1 n-2 n 2 3 n must hold. Definition k.l . Extension of the definition of H(n, p) (cf., Definition 3-2) Define H(n,p) of the. matrix of order 2 where n < p and p = as follows 1 a, 1, ~., 1' 1, 1, ..., 1 H(n, p) = I when n < p, 1, 1, ..., 1 '0, 0, . .., 0, .0, ..., H(n,0) = when p = 0, .0, 0, ..., 0/ _ 3 4- Theorem 4.5 H(n,p) = H(n-l,p), H(n-l,p-l) H(n-l,p-l), H(n-l,p) holds where n > 0, p > 0. Proof . It is clear from Definition 3-2 and Definition 4.1. Definition 4.2 . Extension of the definition K(n,p) (cf., (3-9)) In general, define K(n,p) as follows: K(n ' p) = n C + n C l + '•• + n C p-l K(n,p) = 2 n K(n,o) = when n > p > 1, when < n < p, when n > o, p = o, From Definition 4.2, K(n,n) =2 - 1 K(o,p) =2=1 for p > o > J (*.l) can be obtained, Remark 4.1 . It is clear that the theorems, etc., presented until now also hold if the definitions of H(n,p) and K(n,p) are extended like Definitions 4.1 and 4.2, Theorem 4.6 \ Q = K(n,p) X + X = 2K(n-l,p) 1 IV \_ + _C,\ + \ = 2 K(n-2,p) 2 1 r, r -] +r p 3 1 r x 3 2 ri +r 2 r ! +r 2 +r 3 = 2 3 K(n-3,p) \~ + C,\ + C n \ +...+ C n \ + \ =2 K(n-s.p) sir, s 2 r,+r_ s s-1 r, +r^+...+r , r.+r^+...+r '*' 1 12 12 s-1 12 s \„ + C\ + CLA. +...+ C n \ + \ ■1 n2r i +r 2 n n_1 r l +r 2 + "- +r n-l n"n-l"r-, +r^+. . .+r *r n +r +. . . +r = 2TC(o, p) = 2 holds. Proof, ,U - , U . \ /A, \ / U 1 , U tt/ \ TT /\ TT 1 / n-1' n-1 \ / 1 \ n-1' n-1 H(n,p) = UAU = - 1 n-1 n-1 / \ ;2 ' \ n-1 n-1 A l " A 2 — - U ,, U n -~; — - U A, h Ag n-1 2 n-1' n-1 2 n-1 A 1 - A 2 A 1 ■ + A 2 ^ U n-1 ~ 2 U n-1' U n-1 — 2 U n-1 / holds, where A = A l ° *B On the other hand, since H(n,p) = 'H(n-l,p), H(n-l,p-i; ^H(n-l,p-l), H(n-l,p) holds from Theorem k.5, -36- A- + iL H<n-l,p) = u n _ x — ^ U n-1 (4.2) can be obtained. Therefore, from Theorem 4.3 and Eq. (4.2), \ n + K r = K(n-l,p) \ Q + \ r = 2K(n-l,p) must hold, where r, = 2 Similarly, since 'H(n-2,p) H^^p-l)' H(n-l,p) = H(n-2,p-l), H(n-2,p) holds from Theorem 4.5, k n + X + \ + \ = 2 2 K(n-2,p) ^ r 2 r x +r 2 \„ + _C,\ + \ = 2 2 K(n-2,p) (4.4) 2 1 r r +r v '*' y ' must hold since \ = \ r l r 2 n-2 holds from Theorem 4.4, where r = 2 Similarly, in general, \_ + C..\ + CL\ +...+ C n \ + A. = 2 S K(n-s,p) sir, s 2 r, +r^, s s-1 r,+r^+...+r . r, +r^+...+r 1 12 12 s-1 12 s can be obtained, where r. = 2 for 1 < i < n and 1 < s < n. Accordingly, this theorem holds. 5. SOME PROPERTIES OF C An independent vector in £ , £ , . .., £ , is not determined uniquely, Therefore, independence is defined as follows. Definition 5.1 . Independence of the vector £. Let £. be called an independent vector of £_, £,, . .., £ -, when it satisfies the following condition: £. cannot be expressed as a linear combina- tion of £_, (L , .... £. -, , i.e., there do not exist a_, a,, ..., a. , such that 1 l-l 1 l-l 6 i = a 0^0 + a i C l + '•• + a i-l £ i-l' where a~, a,, ..., a. , are real numbers. 1 l-l Definition 5.2 . Dependence of the vector of £. Let £. be called a dependent vector in £ , £ , ..., C , , when it satisfies the following condition: £. can be expressed as a linear combination of £_, £,, . ... £. -, , i.e., there exist a~, a,, ..., a. 1 l-l 1 l- 1 such that 5 i = a o^o + a A + ••' + a i-A-l' where a_, a,, ..., a. , are real numbers 1 l-l Definition 5.3 . Generator of £_ , C, ..., C , Let £ Q , t^, £ 2 , C p, o.,, C 2. lDe called generators of £ Q , £ , b N-l Theorem 5.1 . When £. (0 < i < 2 S - l) is a dependent vector of C, L, «.., £ . . each of £ (n - 1 > t > s) is a dependent vector of C, , C, ..., L _. . U J- IN — -L 2 +1 ■37- -38- Proof . Since £ . is a dependent vector, £. can be expressed by S i = a C + a l^l + ••• + a l-l C i-l where < i < (2 S - l). Therefore, h B e 2 t = (a o^o + a A + ••• + a i-A-i> E ^ t 2*+l ° 2 t 1 2 t + l "- 1 2^(1-1) where 2 n_1 > 2 1 > 2 S Therefore, from Definition ^.2, £ is a dependent vector of £ , 2 +i ^1' •" , Vl' Theorem ^.2 . When a generator C, is a dependent vector of C, £ . .., t , every £ (0 < i < 2^ S+ ' - 1) is a dependent vector of C, C, . .., £ , . 2 S +i U X W_1 Proof. Since £ is a dependent vector of £_, C, .... C T , , £ can be pS ^ 0' l 7 N-l s expressed by C, = a n £ + a, £,+...+ a £ 2 S ° ° ! 1 (2 S -1) (2 S -1) Therefore, £ » C. = (a n C + a.. L + ... + a £ ) s C. 2 S X ° ° X X (2 S -1) (2 S -1) £ = a £. + a. L ,+...+ a £ 2 S ei ° X 1 iel (2 S -1) ie(2 S -l) can be obtained. Since < i © j < (2 S - l) for < j < (2 S - l) holds, £ 2 S +i is a dependent vector of £ , £ , ..., £ J9- Theorem 5.3 . When £ is a dependent vector ol' i, £ ..., £ N _-,> ^pi+1 is also a dependent vector. Proof. Since C_. is a dependent vector of £_, C , . ... L T ,, 2i 1 N-l C 2i = Vo + & A + "' + a 2i-i rJ 2i-l .'. 5 2± ■ 5 X - (a^ + a^ + ... + ag.^^.^) * ^ can be obtained. Here since < j © 1 < 2i - 1 for < j < (2i - 1), can be obtained. Therefore, C . . is also a dependent vector of £., L, .... 2i+l 1 Vr In general, the following theorem holds as an extension of Theorem $.1 and Theorem 5-2. Theorem 5.h. When £ is a dependent vector of C_. C, . ... L, , , s, s Sfl 0' l 7 N-l 2 +2 +. . .+2 S ^ b is also a dependent vector, for any i, < i < 2 -1 and S l S 2 S i 2 +2 +...+2 +i s > S l > S 2 > ' ' * > S £ - lo Proof . Since £ is a dependent vector of £„. C, . .., C , s, s s « U J- IN - _L 2 X +2 2 +2 ^ £ „ „ = a n^ + a C + o . . + a £ S S B/j 1 1 s s s, s s s, 2 +2 %...+2 * 2 +2 +...+2 -1 2 +2 N-...+2 -1 s s s/ 1 1 1 s s s p s s 2, 1 2 -^2 d +...+2 * 2 +2 -rf-...+2 -1 2 +2 +...+2 -1 can be obtained. Since -40- s l S P S R < j © i < 2 + 2 + ... + 2 -1 holds f or < j < 2 + 2 ■ + . . . + 2 - 1 and for < i < 2 - 1, £ = a J, . + ...+ a £ s, s S/, u i s n s i s /> s r> i s ^ 2 +2 2 +...+2 +i 2 °+2 +...+2 -1 (2 °+2 +2 -l)©i can be obtained, where the right-hand side is the linear combination of £_, £, , S S l S ^ 2 +2 +...+2 -1 Therefore, £ is a dependent vector of C n , C-, , • • • , L T -, ■ s, s . S| u 1 1M-1 2 +2 +...+2 +i Theorem $.5 . When £ is an independent vector of £>„, C, . .., £ , , £. is also an independent vector for any i, 1 < i < (2 - l). Proof . Suppose that there exists a dependent vector £. of £ , £ , . .., £ , . Then h = a o^o + a A + ••' + VA-1 can be obtained, where 1 < i < 2 - 1, Now, l /..s , \ . 11 l-l l-l /r ,s . \ . (2 -l)ei (2 -l)©i accordingly, C = a £ + a, £ + ... •+ a , S _ (5-1) (2 S -1) U (2 S -l)ei X l©(2 S -l)©i (i-l)e(2 S -l)ei holds. Since < j © (2 S - 1) © i < 2 - 1 -Id holds for any j (0 < J <- 2 S - L) and for any i (1 < i < 2 S - l) and for j < (i - l), the right-hand side of Eq. (5-1) is a linear combination of some of t>~, £,;...;£ • Therefore, i becomes a dependent vector of C A , L, X (2 S -1) (2 S -1) •••> Vl' This contradicts the assumption of the theorem. Therefore, £. is also an independent vector of i , £ , ..., i . In general, the following theorem holds as an extension of Theorem 5- 5* Theorem 5.6 . When £ is an independent vector of ^ n , C, ..., S, S Sp (J 1 2 +2 +...+2 -1 C , , £ is also an independent vector for any i, where s-, > s > ... > S| > 1 and 1 < i < (2 - l) . Proof . Suppose that there exists the dependent vector £ of £ Q , i ± , ..., i^_ ± where 1 < i < 2 - 1. Then £ = a C + a i + ... s a s,n s 11 2 +2 +...+2 U lj +i + V 1 + 2 S2 + ... + 2^- 1 ) + i2V 2 + ... + 2^- 1 l(i-l) accordingly, ^ s s s ) E ^ 2 = ( a ^o + ••* 2 X +2 2 +...+2 ^ -l) +i (2 ^-l)©i + a £ ) & t, 2 Sl +...+2 S( ' e " l) + i 2 Sl +... + 2 S(i " l) + (i-l) (2 i -l)©i can be obtained. Therefore, -42- £ = a_£ + a. £ + . s s b- s f 1 So 2 +2 +...+2 -1 (2 -l)©i 1©(2 -l)©i (5.2) + a C, 2 X +2 2 +...+2 ( ^ _l) +i {2 1 +...+2 S( ' e " l) + (i-l}©(2 S ' g -i; ei can be obtained. Since 0<{2+2+...+2*+j)©(2-l)©i<(2+2+...+2-l) holds for any j < (i - 1), where 0<j<2-l and l<i<2-l Therefore, the right-hand side of Eq. (5*2) is a linear combination of some of i~, £,,...,£ . Therefore, £ becomes a 1 s s s, s s s. 2 +2 +...+2 -2 2 +2 +...+2 -1 dependent vector of £ , £ , . .., C N _-,_- This contradicts the assumption of this theorem. Therefore, £ is also an independent vector of £ , £ , ..., £ , . S-. s s« u 1 1M-J- 2 +2 +...+2 -1 Theorem 5.7. When £ , „ is a dependent vector of £_, C, ..., — L ^n-1 ^n-2 ^n-s 1 2 +2 + . . . +2 C T , , it can be expressed as a linear combination of £„, £ , £ , , N-l 0' p n-s n-s+1' £ , . . ., C » that is, 3'2 n - S (2 S -2)2 n - S £ n = a ^^ + a, C + ... + a £ 2 n - 1 + 2 n - 2 + ... + 2 n - S °° X 2 n " S (2 S -2) (2 S -2)2 n - S 2 n " S 2 n_S+1 3'2 n-s a"" 1 + 2 n " 2 + ... +2 n - s = (2 s - ) .n-1 ,(n-s) (2 S - 2)2 n-s where 1 < s < n. Accordingly C t o = a~£. + a,£ + a^£ +...+ a £ _n-l _n-2 ^n-s . i 1 „n-s . 2 ^ ~n-s . /„s \ /r ,s v^n-s . 2 +2 +...+2 +i 2 +i 2-2 +i (2 -2) (2 -2)2 +1 (5.3) n-s can be obtained for any i (0 < i < (2 - l)). Pro of. From Theorem 5.2, £ , _ is a dependent vector of £_, C, ~n-l o n- 2 o n_ s . Cr 1' 2 +2 + . . . +2 +i ..., £ N _ X for any i (0 < i < (2 n-s l)). Therefore, there exist at least 2 n-s dependent vectors in £ , £ , ..„, C Now the generators in £^, £ > £ ■, » C > . . . * £ > 2 n-s' S £ n-s + l' 3 . 2 n-s' V-s)2 n " S Since ^O'^n-1' "'>*> n-s^ 1 1 -1 1 -1 1 1 1 -1 (n-s) 1 -1 -kk- the vectors C>~, i , £ n-s 2 2 quantum vectors , . . . , £ are constructed by the 2 (2 S -2)2~ n-s ll\ and -i/ n Therefore, there exist at most = 2 independent vectors in £_, £ , ' p n-s 7 P n_s C n, .... £ . Here, if and only if the number of elements of each n-B+1' ( 2 s -l)2 n - S ^ is 2 , the number of the independent vectors is 2 . n-s From the description above, there exist at least 2 dependent vectors n ( n— s ) Therefore, the number of elements of each £ is equal to or less than 2 - 2 Therefore, the number of independent vectors in £ , C , £ 5 ,n-s 0' J „n-s' J ^n-s+l' "*' is at most (2 S -1)2' ,n-s = 2' 1. On the other hand, the number of vectors of £_, £ , C -, » Cr p n_s p n-s+ - 1 - £ is 2 . Therefore, £ (2 S -l)2 n - S (2 S -l)2 n - S : ^2 n " 1 + 2 n - 2 + ... + 2 n - 2 can be expressed as a linear combination of £_, C , C n * p n-s' n-s+1' Since (2-2)2 n-s 2 n -\ 2 n - 2 , , a"" 3 > i N n-s holds for any i (0 < i < (2 -. l)), the subscript of each £ of the right-hand side of Eq. (5.3) is between and (2 n ~ 2 + 2 n ~ 2 + ... + 2 n_S - l). Therefore, Eq. (5.3) holds. Theorem $.8 r r 3 • r k k+1 3 k N-r -2r. N-r s k s N-l -• •- N-r -r. s k -45- When every £. for N-r - r u .5 i 5^" 1 - L '-> a dependent vector of (, , i , ..., £ , £„ can be expressed as a linear combination of (, , £ , s k k t , S3. , ..., £ N _ r _ 2 "here ^ > r > r R and ^ = 2 ' , r g = 2 E , (k+1) k s k o n ~ S ..., r s = 2 , . , r = 2 , that is Vr -r. = a 0^0 + a l^r v + & 2^2-r v + '•• + a N-r a -2r,/r Vr -2r^ sk k k s k K s k Accordingly, 5 (N-r -r n )+i ~ a 0^i + a l^r+i + °" + Vr -2r, /r Vr -2r +i x sk k skksk can be obtained for any i (0 < i < (r - l)) Proof o As in the proof of Theorem 5»7^ £ n j £ > ^ , ,, .., ^ r k k *' ^s "k are constructed by the quantum vectors N-r -2r, ? N-r -r, s ^k and each with r, elements. Therefore, the number of independent vectors in £_, £ .> 2 n r k C„ , ..., C T is at most — . Further, if and only if the number of elements k k k ^n of each t, is 2 , the number of independent vectors in £_, £ » ...» (L, is — . 0' r. N-r. r. k k k From the assumption of this theorem, the number of dependent vectors of £-., £-, , ..., C„ -, is at least r + r. . Therefore, the number of elements of each 1 ' N-l s k £ is not more than N-r - r, . Therefore, the number of independent vectors in N-r-r /N-r \ £~, i , (L , . . ., C T is not more than = - 1 1 . r. 2-r/ N-r, r. \ r. / k k k k < \ k / -k6- On the other hand, the number of £_, £ , £_ , .... £„ is r. 2r. N-r -r, N - r k k s k 5 Therefore, C, can be expressed as a linear combination of r n ' N-r -r, k s k b 0' V ' b 2r, ' "' b N-r -2r k k s k Since r l' V '"" V ■"' r k > 1 £ ° holds for any i (0 < i < (r -i))> the subscript of each £ of the right-hand i£— J- side of Eq. (5.^) is between and (n-r - r - l). Therefore, Eq. (5°^) holds, S K. Theorem 5°9 « Let n p,^ n n > n -> ■••* n / \ be as follows: u 1 2 / (n-k;_^s n n : the number of independent vectors of £_, C, . „., ^ TJ _-, in C , C £,...,£ ° 1 ^ (2-1) n, : the number of independent vectors of £_, C, ..,, ^• M _-, 2 k 2+1 2+2 2 U+lj -l n : the number of independent vectors of £ , £ , . .., £ , in ^(* + D< S 2 u + D +1 ' 5 2 (k + D +2 ' •••' ^.^ l / , \ : the number of independent vectors of £_, £, , ..., L T n / 2 (n-k)_ 1 x 1 N-l N-2* N-2 +1 W Then n_ > n n > n > . . . > n / ,\ > - 1 - 2 - - ( 2 ^ ^-1) ~ holds, where < k < n - 1, Proof. It is clear. -U7- • Theorem '■> . LP . Rearrange the generators £ , £., £ , ^ ,., . .., £ n _ L of £ C, ..., £„ in the order. (, , £ , L £ p , ..., £ p . Then the order of vectors after £ becomes: . ... £ ~» £ n <>> ^ ^ > £ i ^ > ^ ^ > n-P n-2 n-1 n-2 n-2 n-1 n-2 n-2 2 2 2 +2 2 +1 2 +2 +1 2 +2 ^ n-1 n-2 ' ''■' n-2 ' n ' ^ n-1 ' ^ n ' 2 n +2 +2 2 -2 2-2 2 -1 2-1 Proof . The vectors after C, in £ , Q , . . . , C have always the factor 2 " in their subscripts and have any combination from 2 ,2 , ..., 2, 1 in their subscripts. Therefore, applying the substitution: 0, 1, 2, 2 2 , ..., 2 n " 2 , S"" 1 A a"" 1 , i, a 1 , ..., s n -3, 2 Q - 2 , , r n-1 to the generators of C, C, . .., L T -, , the vectors after the 2 th have always n-2 n-1 the factor 2 in their subscripts and have any combination from 2 , 1, 2, 2 , ..., 2 in their subscripts. That is, all vectors after the 2 th from ^n-2 t0 ^gCn-D.-g ^ ^ V" 1 ^' 2 ^ ^ ^ ^ &1 ' "'" ^ ^ arranged in the new arrangement. The adjacent vectors ^2 n - 1 + f(2 n - 2 ,2 n " 3 , . . .,£) V^f (2 n " 2 ,2 n - 3 , . . .,2 1 ) + 1 in £ n , £, , ..., ^ TVT _-| (where f (2 I ,2 ,...,2 ) means that some combination n-2 n-? 1 from 2 ,2 , ..., 2 is added) become respectively the adjacent vectors V" 2 + f (2 n - 3 ,2 n "\ . . .,2,1)' V" 2 + f (2 n - 3 ,2 n "\ . ..,2 } ±) + 2 n - 1 after the substitution. Therefore, this theorem holds. -1*8- Example 5 . 1 0, 1, 2, 3, h, 5, 6, 7 , 8, 9, 10, 11, 12, 13, H*, 15 , is rearranged to 0, 8, 1, 9, 2, 10, 3, 11, 1*, 12 , 3, 13 , 6, H* , 7, 13 , after the substitution. Theorem 5-H- r N-2r N-r s - s dependent A V ^l V independent N-r -r N-l s k When every £. for N-r - r < i < N - 1 is an independent vector of 1 S iC L, £, , . .., ^t\t -i an< ^ the others are independent vectors of £_., C, ..., £,, -, , where r, > r > r. , let C T and £, T be expressed by 1 s k N-r N-r -r. s s k C T = a n ^ n + a, £ +a C + ... + a £ o (5-5) N ' r s ° ° X r s 2 2-r s (2 ^_ 2) (2 s_ 2)r ^ s (cf. Theorem 5 .7) and L, = b n £- + 13,5 + b C + ... + b . r (5.6) N " r " r k ° ° 1 r k 2 2-r N-r -2r, /r. N-r -2r SK K K skKsk (cf. Theorem 5.8). Then a. | = 1 for any i (0 < i < (2 - s)) N-r - 2r b. | = 1 for any i (0 < i < ) l — — r. k Proof. From the assumption of this theorem, £. for N-r -r<i<N-l 1 S K is a dependent vector of ± , £., . .., £ . Therefore, of course, £ for N-r < i < N - 1 is a dependent vector. Therefore, from Theorem 5-7> Eq. (5-5) s — — holds. From Eq. (5-5), ( Vr } * ( Vr } = a oVs + a l^r *(N-r ) + "' s s s s accordingly, ^0 = a oVr + a l^r ©(N-r ) + '" (5 ' ?) s s s Substituting £ of Eq. (5-5) to Eq. (5-7), s 2 C = a (a n L + a £ + . . „ } + a n £ /„ \ + .... = a C + a at + 000 1 r lr ©(N-r ) 1 r s s s s (a* - i)£ Q + a a^ r + ... = (5.8) s can be obtained, In Eq. (5-8), the subscript of each £ in each term of Eq. (5-8) consists of r , 2r , .... (2 S - l)r since i • r ©(N-r)<N-r for 1 < i < (2 S -2)r , s' s' ' s s s s - — s Therefore, from the assumption, those £ are independent vectors of £_, £,, ..., £ -. . Therefore, in order to let Eq. (5.8) hold, each coefficient must become zero. Therefore, a o = x Similarly a 2 - 1 1 -50- can be obtained. And, similarly, b 2 = i 1 can be obtained, 6. SOME PROPERTIES OF Z (CF. DEFINITION 3.6) Suppose the following: Condition 6.1 . The independent vectors of C, £-, , £ p , • ••> £ N -, are only i , i v ..., 5 (k . l} , 5 (k . l} , ..., £ (k . l} ; and 5 ± for any i ( 2 k " + £ + 1 2 2 +-L 2 +# (k-l) < i < N - l) is a dependent vector of £,_, i , ..., L -, , where < i < 2 Define V , V, , V_, . . . , V , , x as follows 1 2 (n-k; V, V. tt Q , ^k> - (5 2-2 k' S l' & k ' 2+1 3 k ' 2-2+1 ' £ k } 2-1 A .., £ gCk+D.! > (6.1) .... 5 3-2 k -l V 2 (n_k) -1 ' (C (2 (n - k) -l)2*' ^2 (n - k) -l)2 k ' "" ^^ Definition 6.1 . Z. (cf. Definition 3.7) Define Z_, Z n , Z^, .... Z , , \ as follows 0' 1' 2' (2^-1) 12 .k' k > 1-2+1 ' k (1+1)2-1 Z. = 1 k > 12+1 z k , \ 12 k ej (i-2 +1)< {(i+l)2 k -l}- (1+1)2-1 k > "' i2 Accordingly, -51- UNIVERSITY OF ILLINOIS LIBRARY ■52- Z = V V z i' z 2' -' z (2 (^).x) V Z3 ' "" W^-l) Z iel> Z i»2' ••- ^(n-k)^. (2^-1)' "" Theorem 6.1 . Under Condition 6.1, 2 2 z o = z i 2 2 Z (2 (n " k) -1} := Vn Z ° z. • z. = — z. 1 J nTn 1( holds, where of course < i, j < (2 -1} . V_ Proof . Since the independent vectors of C, , L, . .., L are only in , under Condition 6.1, T T V V = V V = 11 • = V , , , V T , . v =2^ (2 (n-k)_ l} (2 (n-k)_ l} (6.2) can be obtained (cf. Eq. (3.16)). The following relations hold clearly from Definition 3.5, Definition 3.7 and Definition 6.1, that is, -53- I T — v:v. ■± v T v. , -i v T v Vn i ie2 ^ 1 T = — v: ,v. /.. i©i i 4 N le2 l > (6.3) IT IT V n - k) -l} = Vn ViV ie{2 (n - k) -l} ^ Vn V ie{2 (n - k) -l} Vi for any i (0 < i < 2^ n_k ' - l). Therefore, from Eqs„ (6„3)> Z 2 = — V T V n — V^V. = i V T V n V^V. = i V T (2 k E )V. (from Eq. (6.2)) l r i T i NiOOi N l x m ; i v ^ ^ ' ' k k |- -A Z A (from Eqs. (6.3)) = y- Z Q N Therefore, 2 2 z o - z i = = z ^).rl Zo can be obtained. From Eqs. (6.3), Z.Z. 1 J IT IT ITT ^ l0 s[ N ° J N 1 j i V T (2 k E )V. (from Eq. (6.2) N 1 m j 2 k T — V V N i j = ^r: n/n Z. . (from Eqs. (6.3)) = — Z. N i©j ^ i< can be obtained, -54- Theorem 6.2 . Under Condition 6.1, any V. for 1 < i < {2^ n_k ' - 1} expressed by can be and V. = V n A. l l v o = Vi> V. = V.A. l li can be obtained where A = l *j_y a 2 : 0' V a j©i' •••' (2 k -l) (2 k -l) le(2 k -l) >(2 -1) = U, a Oi a li Q 2i a u (2 k -l): U k = 'I, 1 .1, -1 v X % 1 X . . . X (The number of .1, "I, X i .1, -1, y is k. ) Proof. Since every column vector, i.e., £ in V. is a dependent vector of £ , ^1* "*f ^N-l frorri Condition 6.1, £ e V. can be expressed as a linear combina- i2 tion of C, , £ , . .., C ,_ , i.e, '0' =T 2 k -l' ^ k = a^ + a^ + . . . + a^ S^ (6.4) Therefore, -55- (5 k ) « £j = (a C + a^ + ... + ^J^J ■ ^j accordingly ^ k = a (vM + a Aei + ••• + a k ^ k , 12 +j ° J X iej 2-1 (2-1 )®j (6.5) can be obtained for any j (0 < j < 2 - l), where the right-hand side of (6.5) is a linear combination of £ , £ , . .., £ . Therefore, ° X 2-1 12* 12+1 12 +(2-1) ° 1 ' 6 k } 2-1 l 0' <V l 0' a , . . . , a * 2-1 le (^-1) Accordingly, a , a , . . ., 2-1 2-2 V. = V_A. 1 1 (6.6) can be obtained. Applying Theorem 2.1 to A., A. = II A. II 1 k 1 k can be obtained. From Eq. (6.h), «. 2k ) * ? 2 k ■ ^0 + a A + ••• + V-iW B V Accordingly, C . = a~£ , + a, 5 , + . . . + a .. £ . . 1 ° 2 k 1 2 k +l 2 k -l 2 k +(2 k -l) -56- can be obtained. Therefore, similarly, ^5i--W'VW""H ,ii V Q = V.A. (6.7) can be obtained. Therefore, from Eq. (6.6) and Eq. (6.7), V. = V.A 2 l li and 2 V = V A i can be obtained, Theorem 6.3 . Under Condition 6.1, every V i for l<i< (2 ln -l) can be expressed by V. = V n A. 1 1 from Theorem 6.2. Then, A. . = A. -A. can be obtained, Proof. oiiuv -57- ^ V. = V n A. 1 1 V. = V n A. > J J ( V. . = V n A. . i©j i©j (6.8) T T V V = V V A. i 00 T T V V = V V A can be obtained. Therefore, from Eqs. (6. 3), "A Z. = Z n A. l l Z. = Z.A. J j (6.9) can be obtained. From Eqs. (6.9) and Theorem 6.1, ■s/k „ „ n/n Vn i.j 2 T z i z j " ^ ViV; " J \\\\\\\\\\^\ = -f U.A„ A.A.A- U. = -f U. AT A.A.U. = ■— Z^A.A. = Z_A.A. .j^ n k k k ^ n 1 j k o k0ij Oij 2 1 (6.10) where Z = U k A Z Q U k A. = U.A.U. 1 k 1 k A. = U.A.U. J k j k T V_V. . lej " v oVi A j -58- T i©j T V V V A A OOOi j 2^ V. . = 2^ V A. A. (from Eq. (6.2)) m lej m o l j V. . = V_A.A. iej i j (6.11) can be obtained. Then from Eq. (6.8) and Eq. (6.11), put A. . = A. ' A. Theorem G.h. Under Condition 6.1, can be obtained, where a. . = 1 or -1 or V. = V Q A for any i (l < i < 2^"^ - l) Q Oi A. = U, i k a li a (2 k -l)i Without loss of generality, put a. . = 1 or -1 Accordingly, 2 2 A = A = A l A 2 + A' {2 (n ' k) -l} = E, of. From Theorem 6.2, Accordingly, •59- v o = Vi T T V V = V V A i Z " Z A i (from Eqs. (6.3)) (6.12) can be obtained, Let Z-., A. be 0' 1 *\ z o = U k u. 2 k -l and > (6.13) o: Oi A. = U. 1 k a n . li u a 2 k -l)i; J From (6.12) and (6.I3), v. = v.a. . v. (a.. - 1) = (6.14) ■6o- can "be obtained. From (6.14), V. = J or a . . = 1 a. . = + 1 (6.15) can be obtained. Therefore, from Eq. (6.15) and the relation of Theorem 6.1, i.e., 2 2 2 2 i'-^i^-u'Tx ° a.. = 1 can "be determined without loss of generality for any value of V. Theorem 6.5 . The absolute value of characteristic values of Z. for any i (0 < i < 2^ n_k ^ - 1) is equal to or —- . VN Proof . Applying Theorem 2.1 to Z , z o = \ u. 2 k -l / can be obtained. Since holds from Theorem 6.1, 2 2 z °^ z ° 2 2 V. = — V. 1 4k x can be obtained. Therefore, since v.(v. - z- ) = o 1 L s/N v. = or V. = — 1 n/n 2 2 z o ■ z i ■ • 2 2^ = Z {2 (n - k) -l} = N/N Z ° holds from Theorem 6.1, the absolute value of characteristic values of Z. for , i Cn-k) ? any i (0 < i < 2 V ' - l) is equal to or — . VN Theorem 6.6. When /% V. = V_A. = V U J j Ok a 1J Q (2 k -Dj n-k for any j (l < j < 2 - l) under Condition 6.1, if (4 n) ) T e v and V I = S2 + i j holds, where < S < 2^ n ~ k ' - 1 and < i < (2 k - l), •62- (l^.a^-.a e(a ^ ) - (4 n " k) ) T holds where u = fu (n) u (n) J n) ) =-i (V n > a (n) e (n)> ) cf. Definition 3.5, Proof. Since (°)V e V (4 B) ) I = S2 k + i holds from the assumption f| D) ) T =(W f). (4 n " k) ) T (6.16) can clearly be obtained. Therefore, v . (^ holds . Let the ith row vector of V. be v. J 1 Since V. = V n A. '1 ^S can be obtained. Therefore, from Theorem 2.2, / (k)\T A / (k)Vr v. = in. J A. = a. . I u. ' J can be obtained. Therefore, fu (n) \ T - ^u (k)T a u (k)T a u (k)T a u (k) V U I ) ~ \^i ' a il u i > a i2 u i "•"' ^(n-k)^ u i T ( (k) T (k) T (k) T \ , n = u ,u. ,...,u. a (i,a.,,a. n , . . .,a , , \ \ i i i / ' il' i2' ' i(2^ n '^-1) (6.17) can be obtained. Therefore, from Eq (6.16) and Eq, (6.17), il' i2' i(2^ ^-1' (4 n " k) ) can be obtained. Condition 6.2 . Suppose that there exists £. for a suitable i (0 < i < 2 - l) corresponding to A. for any j (l < j < 2 - l) such that J CI Oj a (k) _ lj a 2j a (2 k -l)j where -6k- A. = U, J k Q Oj \ a io ° a 2j a (2 k -l)j (cf . Theorem 6.2). Theorem 6.7 . Let A. be a i' V •••' a , k (2^-1) «!, A. = J a , a , . . ., a J le(2 -1) '*' ^' '•" ^(2 k -l) (2 k -l) • • • :. a Q and Under Condition 6.2, a=a=...=a. ,=a. n =...=a . =0 o i i-i 1+ i (2 k_ 1} a. = 1 l can he obtained. -65- Proof . Ap] g Theorem 2.1 to A. J a - -±- (a a a )u (k) - -A- ^ (k) Vu (k) - fu (k) Y r u (k) ^ J° J 1 j(2 can be obtained. Therefore, &n = 1 when £ = i a.g = when £ ^ i can be obtained, Now, in the case of a group code, it is found below that Condition 6.1 and Condition 6.2 are satisfied., (n) T (n) T In a group code, if there exist row vectors of V in ui. , u , ..., ( n ) J ■ ( n ) ( n ) ( n ) +^ ^ ^ 4- * u / , N and xn u / , \, u / , \ , . .., u. T ' , the number of row vectors of 2 (n~l)_ 1 2 (n-l)' 2 (n-l) +1 ' TJ-1 (n) (n) ( n) * V in ul , u, ..... u , , \ is equal to the number of row vectors of V 1 2^-1 . (n) T (n) T (n)' 1 ' inU 2 (n-l)> U 2 (n-1) + ^ — Vl ■ T Similarly, in a group code, if there exist row vectors V in u^ , f \? ( > T " '■ \ T ( \ T f \ T (n) \ n ) ^ • l n ) l n ) ( n ) \x: , .c., u . ana xn u , u , ..„, u , , \ , the number of row vectors 1 2-1 2 k 2+1 2 U j -l ( i ( i f > of V in u. , v.: ..-.., u \ is equal to the number of row vectors of V 1 2 k_ x (n) T (n^ T (n) T in u . , u . , .... u /. , \ . Therefore, if there exist any independent 2 k 2 k +l 2 (k+l) -l vectors of £ , L ,...,£ 'in £,£,..., £ , and in £ , U 1 W_1 £2 £2+1 (£+1)2-1 (£+1)2* £ , , . .., £ , , the number of independent vectors of £_, C, „.., (£+1)2+1 (£+2)2-1 ° X E_ , in £ v ; 5 v j ..., 5 , is equal to the number of independent W_1 i2 K £2+1 (£+1)2-1 vectors of C, t, „„„, C in £ , C ,...,£ fc . U X W 1 (£+1)2* (£+1)2+1 (£+2)2-1 -66- Therefore, since the total number of group codes is of the form 2 , if there exist independent vectors of £ , £ , . .., C in £ , £ , . .., £ , t ~ the number of independent vectors is of the form 2 (t < s). Therefore, applying Theorem 5-10 a suitable number of times to £_, £, , . .., L and renumbering the subscripts in natural order from the first vector, only £_, C , £„, . ... £ are independent vectors of £_, £, , .... C T .. and the others are 2 / s -, \ 1 N-l dependent vectors of £~, £ , ..., £ -, . This is Condition 6.1. Now, consider uj , u' , u t where a b c "N I = S 2 + a a a K = S . 2S + * f I = S 2 + c C C y (6.18) and < S , S, , S < (2^ n_S ' ) - l), < a, b, c < (2 S - l] 3, D C Assume that b c (6.19) holds. (There always exists I such that I ©1=1 is a group code.) Therefore, from Eq. (6.18) and Eq. (6.I9), S 2 S + c = (S © Sj2 + (a © b) c a b • • o — o © o_ cab c = a © b "\ > (6.20) y can be obtained. Applying The ore i: 6.1 bo Eq. 6.20, .(n-s) < p(n-s) _ ^(n-s) m ^(n-s) 'S ®S, S a b a (6.21) can be obtained. Now, ui ' € V can be assumed without, loss of generality. Therefore, Eq. (6.21) means that Condition 6.2 is satisfied. Remark 6.1 . In the case that Condition 6,1 and Condition 6.2 are satisfied but the code is not a group code, S = S © S,_ cab is satisfied but c ^ a © b holds (cf. Eq. (6.20) Remark 6,2. When V satisifes Condition 6,1 and Condition 6.2, and % a (k) = i lj :t 2j a (2 k -i)j holds (cf. Condition 6.2), [a 0J ,a lri ,a 2J ,...,a } -68- becomes an Abelian group under the operation of multiplication. Accordingly, considering the matrix a 1, X, 1, 1, ..., 1 a = 1, a 1±f a ±2 , 1> ^l' Q 22' a iV '••' a n-k) 13 l(2 n kj -l) Q a S3' ••" 2(2^).^ l, a k , a k (2-1)1 (2-1)2 . . ., a *-i)(2 (n - k) -i) (as u^ e V can be assumed without loss of generality, it may follow that 01 02 that = a o( 2 (n - k) -i: = l) there exist i_, i , . .., i / , \ such (2' •) ,(k) (k) (k) (k) 1 2 {2 ( n - k) -l} from Condition 6.2. From Theorem 6.6 and Condition 6.2, Ct is reduced to the following form: a (n-k) '0 (n-k) T (n-k) T (6.22) -6 9 - Since {1,Q. .,&,..„,., a ) is an Abelian group as mi i<;d abo U 2j (2 k_ i} . f, (n-k) (n-k) p(n-k) " S k 2-1 becomes an Abelian group under the operation "h 1 7. SOLUTION OF EQ. (3=25) "VA'V T = 0" UNDER CONDITION 6.1 and CONDITION 6.2 Even if generators of £ n , £,, , .., £ , are rearranged in any order, m Eq. (3-25), i.e., VA'V" 1 " = 0, holds. Let the transformation of the rearrangement of generators of £ n , £, , . „., C be t, that is, V'T = W From Theorem 4.U, A' is invariant under the transformation, i.e., tA*t T = A' Therefore, WA*W T = VTA'T T V T = VA'V T = (7.1) can be obtained. T Since it is clear that A. = A. holds from Theorem 6„3> 11 VA>V T = (V ,V A 1 ,V A e ,...,V oA(2(n . k) ^ i )A-(y o ,V A 1 ,.„. ) V A [2(n _ k) ^) T " V A + VA + V2 A 2 + -• + A (2 (^). 1) A [2 (n-k). 1 , A {2 (n- k )_ 1) > V " ° Accordingly, V (A + A AAl + A 2V2 + ... + \ 2 (n-*)_ 1) \ 2 (n-K)_ 1) \ 2 (n-K)_ 1] »0 )V* = (7.2) can be obtained, where -70- where A) A, A' a A 2 (n " k) -l} Considering Theorem 6.7, let A. for any j (l < j < 2 - l) be V V ••" a 2 k_ x . i©l . /^k i©(2 -1) > (7A) a o ~ a i a , , . „ . , a 2-1 ° i.-l i.+l n k , J J 2-1 a. = 1 i . J J < i. < 2 - 1 - J - (7 = 5) Since \' J2 A. J X ' k J2%1 X ' k k J2 +2-1 holds from Eq. (7=3), -72- V k J2 +i. A.' A.A.A. = J J j2 +(l©i ) J (7.6) \' [j2 k + i? k -l)©i can be obtained from Eq„ (7°*0 Therefore, let A n + AAA + ... + A f x A / . v A , . x 1 1 ( 2 (n - k) -l) {2 (n - k) -l} {2 (n - k) -l} The following relations can be obtained: (2 k -l) (7,7) ° ° 2 k + i x 2.2 k + i 2 3 '2 k + i 3 + ... + \' In general, (2 (n-k)_ 1)2 k + . > i2 (n - k) -l} v . = \ \ + \ ' + ^'v + . . . + \ • / . * . y 3 2%(jei ) 2 <2 k + (jei) {2 (n - kj -l)2 k + { jei , . , } ^ {2 U_k; -l} where < j < (2 K - 1) y (7.8) -73- Now, the solution such that the number of most efficient codes if; is discussed below. Theorem 7.1 . In Eq. (7-8), when V Q = 0, (7.9) V. = J can be obtained for any j (0 < j < (2 -l)) Proof. Applying the result of Theorem 3.1 to Eq. (7-8), in) (n) (n) (h^h i; . ..^(u + ay 4- ... + a , +1 1 t2 - 1>Z +X i2 ("-*). 1} can be obtained, where h' = h - 1 = 0. Since (k) (k) (k) 1 Cg^^-l] is an Abelian group from Remark 6.2 whose generators (i.e., bases of the Abelian group) are |< k > , (« |W l« ... tj^j, u ° > +il + - + V n - k) -i^ + i , >, (7ao) . (n) + u ( "> V /(n) \ /(n) (n) (n) (n-k-1) d +1 fn.lr.l , -7k- can be obtained. Since u' n is the column vector of U , the elements of (u^ + u^ x n \ i are or 2, I.e., non-negative in general. Therefore, letting P \ the right-hand side of Eq„ (7.10) \ X N-1 / (7.11) x. > l — (7.12) can be obtained for any i(0<i<(N-l)) From Eq. (7.9) and Eq. (7.H), V Q = (h',!^.,,,!^) "N-l, = Vo + h l X l + ••• + Vl X N-l (7 ° 13) can be obtained. Therefore, when V = holds, h. = 1 rhen x. f 1 ' can be obtained from Definition 3.2, Eqs. (3. 5) and (7.12) Now, from Eq. (7.8), (7.14) V i = X \ + A 'k + '•• + X ' (n-k) k 2 'N(jei L ) {2 (n ~ k) -l} = (h',^,...,^) u + (n) „(n) + „ „ . + u 2 +(jei 1 ) (n) (2 (n - k) -l}2 k + Uei ) (2 U kj -l] = (h^,...,^) (n) u + u + ., 2 K± 1 + u {2 (n-k)_ 1)2 k + . » u (n) [2 (n-k)_ (h^,...,!^) / X ° \ (n) u . J X N-l (from Eq. 7.10) and Eq. (7.11) X U 0j = (h^h^^h^; x,u, . 1 lj X N-l U (W-l)j h X U 0j + h l X l U lj + -° + Vl) X (N-l) U (N-l)j = (from Eq. (7.14)) can "be obtained, Now, in the solution of VA'V = such that the number of most efficient codes is 2 , det V Q £ can be obtained- Therefore, from Eq. (7.2), A + A 1 A 1 A 1 + A 2 A 2 A 2 + ' -76- A {2 (n - k) -l} A {2 (n - k) -l} A (2 (n - k) .~l} = can be obtained. Therefore, from Eq. (7.15) and Eq„ {7.7), (7.15) (2 k -l) (7.16) can be obtained. Therefore, the problem can be reduced to that of obtaining maximum k such that Eq, (7.l6) holds, Accordingly, from Theorem 7.1 the problem can be reduced to that of obtaining maximum k such that V = 0. Theorem 7-2 . The problem of obtaining maximum k such that V = can be reduced to obtaining a solution in non-negative integers x, , x , . .., x , k, for the equations \„ + x, X' + x„\ 1 r 1 2 (r 1 +r g ) . + x \, \ n ( r, +r^+„ . „+r ) 12 n (7.17) 1 + x n + x^ + „ . „ + x =2 12 n (n-k) (7.18) which maximizes k where -77- (I) when k > (n - k) 1 - n-k 1 1 2 - n-k 1 n-k 2 X l + X 2 + + x , < , C i + i C o + n-k — n-k 1 n-k 2 x, + x„ + . . . + x . . < 2 1 2 n-k+1 - (n-k) _ x (n-k) + + x < . C n n — n-k n-k ^ + vC > - 2 (n " k) - : n-k n-k o( n -k) -, X] _ + x 2 + . . . + x k+1 < 2 - 1 x + x + ... + x. . + x, _ < . C + C_ + . .. + C . 2 3 k+1 k+2 - n-k 2 n-k 3 n-k n-k x, + ... +x. . +x, , < ,C. + , C, + . „ „ + C . 3 k+2 k+3 - n-k 3 n-k k n-k n-k > (7.19) J ■78- (II) when k < (n - k) 1 — n-k 1 x, + x_ < .C. + C_ 1 2 — n-k 1 n-k 2 x. + x + x_ < C. + ,C. + . C_ 1 2 3 ~~ n-k 1 n-k 2 n-k 3 X l + X 2 + + x. , < . C n + .C. + k+1 — n-k 1 n-k 2 + n-k C k+l X 2 + + x. , + x. _ < . C + , CL + . . . + , C. _ k+1 k+2 - n-k 2 n-k 3 n-k k+2 x 3 + + x. _ < . C_ + . . o + , C. _ k+3 _ n-k 3 n ~k k+3 x _. + . . . + x . < . C _.+...+ ,C n-2k n-k — n-k n-2k n-k n-k n-2k+l n-k+1 — n-k n-2k+l n-k n-k ^ V (7.20) x ,+...+ x < ,C . n-k n — n-k n-k J and where and r\= 2 , r_ = 2 , . . . , r , = 2 , r =1 1 '2 n-1 n :, f x , ..., x are non-negative integers Remark 7.1. Equation (7-17) is an indefinite equation of n variables (x v x , 1' 2 ; .... x ) of the first order. Therefore, the general solution can be always 7 n i:ied. First, obtain a bo1u1 ion for maximum k L] tie general solution bui that Eq. (7«l8) is satisfied. Then the conditions, i.e., k>n-kork<n-k are determined. Next, investigate whether the solution satisfies Eq. (7.19) or Eq. (7.20) corresponding to the conditions k > n - k or k < n - k, respectively. If the solution does not satisfy Eq. (7. 19) or Eq. (7=20), obtain the solution about the next maximum k in the general solution such that Eq. (7»l8) is satisfied. Continuing the precedure, the solution for maximum k such that Eq. (7ol8) and Eq. (7. 19) or Eq. (7.20) are satisfied, can be obtained. This is the desired solution. Proof of Theorem 7.2 . In V (cf. Eq. (7-8)), since < ± ± < 2 - 1 (cf. Eq. (7°5))> there exists a possibility that A' = A' or A' , or . ,., 2 +i 1 r l r l +r 2 or A (cf. Theorem 4.4). A similar possibility exists with respect r +r +. . .+r r l 2 k+1 to X ,, , \ , A' / \ ,„..,A'/ \ . Therefore, the number of (,K+±J [k+d) (,n-±J . 2 +1 2 2 +1 2 2 2 +1 2 (n-k-l) A' having the possibility is , C, . n-k 1 Next, there exists a possibility that A' = A or A' 3'2 k + i r l +r 2 r l +r 2 +r 3 3 or .... or V A similar possibility exists with respect to r +r +„ . . +r 1 2 k+2 A' , A , ..,, and the number of A 1 which has the possibility is C 1- r^k . /■ „k . n-k 2 6-2 +i 6 Continuing the discussion, Fig. 7=1 and Fig. 7.2 can be obtained 5-2 +i c 6-2 +l c 5 o corresponding to k > n - k and k < n - k, respectively. In Fig. 7.1 and Fig. 7.2, (i) and (i)2 + j mean, respectively, A' and A' , r, +r +. . .+r . / ^k . 12 1 (r +r +. . . +r. J 2 +j As shown clearly in Fig. 7.1 and Fig. 7.2, the conditions (7.19) and (7.20) can be obtained corresponding to k > n - k and k < n - k, respectively. Equation* (7.17) is also satisfied. -80- , , k (D(2)(3) (1)2* + i (2)2 k + i (3)2 k + i (n-k)2 K + i X l X 2 x 3 "n-k L k+1 Figure 7.1. (k > (n - k)) (1)2 K + i (2)2 k + i (3)2 k + i (1)(2)(3) (n-2k) (k) (k+1) (n-k)(n-k+l (n) (k + l)2 K + i (n- k)2* + i Figure 7-2. (k < (n - k)) -81- Since the number of terms of the right-hand side of Eq. (7*8) 2 (n-kJ^ it is ciear that Eq> (7.i8) must hold. Now, suppose that maximum k and x , x , „ . . , x such that Eq. (7.17)* Eq. (7.18) and Eq. (7.19) or Eq. (7-20) are satisfied, have been obtained. From Eq. (7.19) and Eq, (7/20), x n < . C, 1 - n-k 1 holds. Therefore, x, of the elements \\ , X ' . , X\ _. ,..., 1 o k • o k+1 • n k+2 • 2 +i, 2 +i 2 +i 2 \' / , \ , can take the value \' . It is quite arbitrary which of them 2 (n-k-l) take the value A,' . r l Therefore, let x, of them take the value A,' . 1 r l Next, let x of the others whose number is ( , C, - x, ) and \' , , (— n— K -L -L A 3°2 +i A.' , . . . , in general A, 1 , take the value A' . Since 5°2 +i (2)2+1 r l +r 2 x, + x_ < , C. + C_ 1 2 — n-k 1 n-k 2 holds from Eq. (7.19) & n( 3- Eq. (7.20), the procedure is always possible. Continuing such a procedure (it is always possible since Eq. (7.19) and Eq. (7.20) hold corresponding to k > n - k and k < n - k, respectively and Eq. (7.18) holds), the value of each term of the right-hand side of Eq. (7.8) can be determined and V = holds from Eq. (7.17) ° Then, of course, i, , i , V ., can also be determined, Remark 7 » 2 . The values of i, , i , ..., can be determined as shown in the proof of Theorem 7.2. Since -82- V n = V.A. J J holds for any j (0 < j < 2^'^ - l) from Eq. (6.7), C = C = C ° V.i. J £ * + i. J J (7.21) can be obtained from Theorem 6.7, Therefore, from Eq. (7.21) ^ JS +(i.el) J 2 k J2%(i ®2) J > 2 k -l j2 k +{i e(2 k -l)} (7.22) can be obtained. Therefore, j2 +i. J j2 k +(i.©l) J = z j2 +(i e2) J 1 Z =7 2 k -l j2 k +{i.e(2 k -l)j J J (7.23) can be obtained. Now, from Theorem 3.1 and Eq. (3.27), -83- ZA'Z = U U A'U n n vj u k N-l / X = u (H(n,p) - E N ) k N-l x N-l U = Accordingly, / x. (H(n,p) - E N ) U-l = (7.24) Hf-1 can be obtained „ .(n) T Equation (7.24) means that when x. is identically zero, u^ 11 £ V (n) T "" and when x. is not identically zero, u. e V, l i On the other hand, applying (Theorem 2.1) to Z, x. =>Tw (vv-" z N-i )u i (n) (7.25) can be obtained, for any i(0<i<N-l). Therefore, it is possible from Eq (7.23) and Eq. (7.25) to find .(n) such that ■8k- u. n) £ V. when x. £ 11 l r u' n ^ jt V. when x. = 1 i i J (7.26) Therefore, all the codes corresponding to the binary expression of i such that x i ^ are the set of most efficient codes under the conditions. Remark 7.3 . In general, 2 < the number of most efficient codes < 2 n_P+1 holds (cf. Y. Komamiya: Bulletin of Electrotechnical Laboratory, Vol. 17, pp 298-3IO, 1953 and Proceedings of the Third Japan National Congress for Applied Mechanics, 195*0- Therefore, letting K Q be a maximum k, 1 5 K 5 n - P + ! (7*27) can be obtained. Remark 7.4 . When there exist A , A , ..., A , v satisfying Eq. (7.15), d (2 ln " iJ -l) + A , + A .., + A , x also clearly satisfy Eq. (7.15). 2 {2 ln ~ RJ -l) Example 7.1 . The case of n = 3, p = 2. From Theorem k-.k and Theorem 4.6, \>- k A. r l 2 X r i +r 2 \ r 1+ r 2+ r 3 -2 •85- Accordingly, "\ *0" 3 \' = 1 T +T 12 r l +r 2 +r 3 = -1 = -3 (7.28) J *0-3 K =X 2 =X h =1 3 5 6 V" 3 (7.29) can "be obtained. Applying Theorem 7-2 to this case, >v 3 + x 1 - x 2 - 3* 3 = 1 + x, + x + x_ = 2 J (7.30) From Eq. (7-27), k<n-p + l=3-2 + l = 2 can be obtained. Now, let k be 2, i.e., ■86- k = 2 (7-31) Therefore, from Eq. (7-31) and Eqs. (7. 30), X l " x 2 " 3x 3 + 3 = ° -\ X l + X 2 + x 3 " X = ( x 3 = l X l = x 2 ■ " ° can be obtained. From Eq. (7.31), k = 2>n-k=3-2 = l (7.32) k > n - k (7.33) can be obtained. It is shown below that Eqs. (7.32) satisfy Eqs. (7.I9) X l = X-, = X l + X 2 X l + X 2 + x 3 x 1 + x 2 + x 3 °-S c i < 2 n ' k -1=2 < 2' -1=1 1 < 2' -1 = 1 1 5 i c i " x "\ -1 = 1 J Therefore, since t2 (n " k) -l) X 4 = 3 (7.3i*) -87- can be obtained. Therefore, from (7-23)> z = Z 7 -\ Accordingly, z l " z 6 \* z 5 Z_ = Z, 3 ^ J X (7-35) can be obtained. Therefore, from Eqs. (7-35) and Eq„ (7.25), x = V8 x, = -f~8 x £ = ^8 x -^8 x, = -Jq x = ^8 = ^8 X 7 = z Q + z x + z 2 + ... + z ) = 2vT8 (z Q + z 1 + z 2 + z ) ^ z " z l + z 2 ' z 3 + z 4 " z 5 + z 6 " z 7 } = ° z + z l ' z 2 " z 3 + \ + z 5 " Z 6 " z 7 } = ° z " z l " z 2 + z 3 + z 4 ' z 5 " z 6 + z 7 } = ^ (z ' z l " z 2 + z 3 } ^ ° z + z l + z 2 + z 3 - \ - z 5 ' z 6 " z 7 } = ° z " z l + z 2 " z 3 " \ + z 5 " z 6 + z 7^ = ( z - z x + z 2 - z^) ^ z + z l " z 2 - z 3 " \ - z 5 + z 6 + z 7 } = ^ 8 U + z l " z 2 " z 3 } ^ ° z " z l ' z 2 + z 3 " \ + z 5 + z 6 ' z 7 } = ° can be obtained. Therefore, x n ^ 0, x ^ 0, x ^ 0, x-r ^ can be obtained, Therefore, the most efficient codes are -88- [° 1 1 1 1 1 1 (7=36) Example 7*2 . The case n = 3> P = 3 From Theorem k.h and Theorem h.6, K^6 \ r. r +r 12 A.' r +r +r 12 3 = > = J (7.37) can be obtained „ From Eq. (7-27), 1 <k< 3 - 3 + 1 = 1 can be obtained. Therefore, in this case, k = 1 can be obtained. Applying Theorem 7.2 to this case, 6 + x 1 * + x (-2) + x • = 1 + x + x + x = 2 = ^+ J- <- j x l " x 3 " ° x 3 = 3 "\ (7.38) (7.39) can be obtained. -8 Since n-k=3-l = 2 and k = 1 hold, k < n - k can be obtained. It is clear that Eq. (7-39) satisfies Eq. (7.20). From Eq. (7-8) 1 2 +i 2 J 3 can be obtained. Therefore, from Eq. (7. 39) t \ 2 + i 1 = 3 2 + i 2 = 5 > 3-2 + i = 6j Accordingly, •i- 1 Si" 1 i 3 = o can be obtained. Therefore, from Eq. (7.23), z o = z 3 = z 5 = Z 6 z l = z 2 = z 4 = z 7 (7.1*0) can be obtained. Therefore, from Eqs. (7.U0) and Eq. (7.25), ■90- x ^0 x ? f "\ \ x l = x 2 = x 3 = \ = x 5 = x 6 = ° . (7A1) can be obtained. Therefore, the most efficient codes of this case are '0 a i i, (l.h2) 8. GENERAL SOLUTION OF VA'V T = Since Z = -i (1,1,. ..,1)6 VN (8.1) holds from Definition 3-6, (n) .(n) 1 = vN (z_, z, , . . ., z_ T n )u. = 1 when uY Cr 1 N-l i l :. -Vm (z ,z 1 ,...,z n _ 1 )u^ = when u[ n) ft V > (8.1') v can be obtained, where / x r Z = U u x N-l (cf. Definition 3.7). Therefore, x Q = x ± + . . . + x = m (8.2) can be obtained where m is the greatest possible number of most efficient codes Since z ^(i,i,...,iK , z o = m n/n (8.3) can be obtained. -91- -92- Now, the discussion from Eq. (7-24) to Eq. (7.26) holds in general. Therefore, letting the number of x. such that x. - be a, 7 ° l l m = N - a (8.4) can be obtained. Since each z. for any i (0 < i < N - l) can be expressed as a linear combination of x fi , x-,, . .., x , from Eq. (8.1), "a" elements of z , z,, . .., z can be considered the independent variables. From Eq. (8.4), in order to let m be a maximum, it is necessary to let a be a minimum, that is, max(m) = N - min(a) (8.5) Now, let the relation among z , z , ..., z obtained from Eq. (3«27)> i.e., ZA'Z = be R or R or R or ... (8.6) If the relation in which the number of independent variables among z , z , z , ,.., z is a minimum is selected among the relations R , R , R , ..., the number is max(N - a), i.e., max(m). Example 8.1 . The case n = 3> p = 2 This case is Example 7-L Here, the case will be solved by the method developed in this section. From Eq. (7.29), -93- s> ' 3 \ X i = K " K ■ x S " S " ^ " - 1 >• *} - -3 _ holds. Therefore, from the equation ZA'Z = 0, Vl " Z 6 Z 7 z o z 2 = Z 5 Z 7 < Z Z 3 = \ z l + Z 5 Z 6 ' z l z 2 Z Z 4 " Z 3 Z 7 Z Z 5 " Z 2 Z 7 + Z 3 Z 6 " z l z 4 Z Z 6 = z l z 7 + Z 3 Z 5 " Vk r z l z 3 = V< < z l z 5 = Z 2 Z 6 v. Z 2 Z 3 = V 5 (8.7) (8.8) (8.9) (8.10) (8.11) (8.12) (8.13) (8.14) (8.15) . 9 k- r 3( Z ; 2, 2 2 2 Zy) + z i + z 2 " It f 2 2 2, . ^ z 3 + z 5 + z 6 ) = 3(z 2x 2 2 2 " z ^ - z 3 + z^ 1 " V + z o < ^/ 2 2x 2 2 2 3(z 2 - z 5 ) + z 3 + z Q + z 6 ,2 2 2v ^ Z 2 + \ + v (2 2 2, (z l + z 7 + V v nt 2 2v 2 2 2/2 2 2-. 3(z 3 - z^) + z 2 + z x + z - (z Q + Zg + z J = (8.16) = (8.17) = (8.18) (8.19: can be obtained, Substituting (8.7), (8.8), (8.10) in (8.9), (1 - #<v 3 v< = (8.20) can be obtained, Similarly, substituting (8.7), (8.8), (8. 10) in (8. 11) and (8.12), (1 ~I )(z z 5 z o z 3 z 6 ) = (8.21) (1 z o z 3 z 5 ) = (8.22) respectively can be obtained. From (8.20), (8.21) and (8.22), /r s 2 2 (I) z ? = Z Q I I V 3 = Z 5 Z 6 Z Z 5 = Z 3 Z 6 ^ Z Z 6 = Z 3 Z 5 (8. (8.2*0 (8.25) can be obtained. From (II), 3 2 2 2 V 3 Z 5 Z 6 = Z 3 Z 5 Z 6 Z 3 Z 5 Z 6 (z 3 Z 5 Z 6 ' z } = can be obtained, Therefore, ll. l) ^5 Z 6 = or (II. 2) z^z 6 = Z can be obtained, In (11,1), when z = 0, from (8.24), (8.25), z 5 = z 6 = ° can be obtained. Similarly whe z,_ =0, z^ = z r = can be obtained, and when 5 3° z^ =0, z = z = 0, Therefore, when (ll.l), z 3 = z 5 = z 6 = ° (8.26) can be obtained. Therefore, from (8.7), (8.8) and (8.9), -96- z l = z 2 = \ = ° (8=27) can be obtained. Therefore, from (8.16), 2 2 Z 7 = Z can be obtained. Therefore, (II. l) can be reduced to (i). Therefore, only the cases (l) and (11.2) may be analyzed, (i) The case z_ = z holds. (1.1) When z ? = z Q Z 7 = ± Z z l = z 6 (8-28) z 2 = z 5 (8.29) \ = z 3 (8.30) can be obtained. These relations, i.e., z ? = z Q , (8.28), (8.29), (8.3O) clearly satisfy the relation (8.13) to (8.19). Therefore, in this case, the number of independent variables among z Q , z ± , . .., z is 4. Therefore, the greatest possible number, i.e., max(m) = k can be obtained. As in Example 7.1, using the relations z = z , (8.28), (8.29), (8.3O) to *j =^N (z , Zl ,...,z 7 )u. x = lf x 3 = 1 ' x 5 = 1 ' x 6 = ^ x i = x 2 = x 4 = x 7 = ° can be obtained. Therefore, the most efficient codes are JO \ 1 1 1 1 1 1 (1.2) z ? = -z Q From (8.7), (8.8), (8.10), z l = " z 6 ^ Z 2 = " z 5 > \ = " z 3 J (8.31) can be obtained. These relations, including z_ = -z , clearly satisfy the relations from (8.13) to (8.19). Therefore, in this case, the number of independent variables among z , z , ..., z 7 is h. Therefore, the greatest possible number, i.e., max(m) = h can be obtained. From z = -z and (8.31), similarly x l ~ x 2 ~ x k ~ x 7 " - 1 x,-, — x~ ■• X,- —■ X/- ~" u 0356 can be obtained. Therefore, the most efficient codes are -98- 1 1 1 1 1 1 (II. 2) The case z z n z A = 3 5° From z z z^ = z n and (8.23), 3=3 Z Z 3 " z o 3 2 Z 3 = Z C" Z = ~f> (Cf. Eq. (8.3))) (8.32) can be obtained. Similarly (8,24) and (8.25), 2 2 2 2 Z 3 = z 5 = z 6 = z o (8.33) can be obtained. On the other hand, from z^z^z A = z^ > ( ' . * z„ = — > 0) 3 5 6 ^ z > \ "\ z 3 >0 z 6 >0 y z r < . 6 y *\ z 3 <0 . > y or z,_ < r or z._ > Y 5 [ 5 1 5 z r < 6 ^ > V z < o ; z g >0 y must hold. Therefore, z 3 = z 5 = Z 6 = z or ■"•'- z 3 = " z 5 = z 6 = z or " z 3 = Z 5 = " z 6 = z or " z 3 = " z 5 = z 6 = z can be obtained. Therefore, from (8„7)> (8.8), (8.9) and the above relations, or or or Z l " z 2 " \ ~ T r Z 3 " Z 5 " Z 6 " Z Z l " Z 2 " ~\ ~ ~ Z T Z 3 " " Z 5 " " z 6 " Z " z l = Z 2 = -\ = V " Z 3 = Z 5 = " Z 6 = Z z, = -z^ = -z, = z„, -z„ = -z r = Z A = z 1 - * 2 " h " "7' 3 ' 5 " 6 " "0 can be obtained. These relations also satisfy the relations from (8.I3) to (8.I9). Therefore, in these cases, the number of independent variables amon£ z , z , . . . , z is 2. Therefore, the greatest possible number, i.e.^ max(m) = 2 can be obtained. -100- Calculating x ± = VN (z Q , z^ . . . ,z )u. by using these relations, the following results can be obtained: o\ /l \ /0 1 0\ / 1 i i i/, \0 1 1 / , \l 1/ , \ 1 1 Finally, max(m) = 4, the greatest possible number, that is (i.l) and (1.2), can be obtained. 9. GENERAL SOLUTION OF VA'V T = IN APPLICATION OF BOOLEAN ALGEfc T A necessary and sufficient condition that VA'V = is that x.x.h. . = (9.1) i J i®J when i ^ j (0 < i, j <* 2 n - l), and that x 2 h' = for < i < 2 U - 1. 2 Equation (9.1) follows from Eq. (7.24), and x.h' = because h' = 0, Since x. = 1 or holds for any i(0<i<2 n -l) from Eq, (8.1 1 ), x. can be considered as a variable of a Boolean function. l In order to satisfy Eq. (9.1). when h. . = 1, x.x. = must hold, but lej ' l j when h. . = 0, the value of x.x. may be arbitrary. i©j i J J J Therefore, when h. . = 1. lej x ± x. = (9,2) .'. 7, v y . = 1 (9-3) J must hold for any i / j (0 < i, j < 2 - l), where y. is a negation of x., "N y. = x: ^i i > (9.4) y. = x J Therefore, 0<i ,j<£ n - -l n (*i \s V = 1 h. i .=i (9.5) -101- -102- must hold. Therefore, after the expansion of Eq. (9»5)> choose the term whose number of variables (y.'s) is minimal. Now, suppose that the term is y, y, ...y, (9.6) Then if y, y, ...y, - i (9-7) X l X 2 ^ holds, y, - y, = ... = y. = l (9.8) x i x 2 ± i can be obtained. Therefore, from Eq. {9 .h) and Eq. (9-8), x. = x. = ... = x. =0 (9.9) X l X 2 H can be obtained. This means that ifx. =x. = ... = x. =0, X l X 2 H VA'V T = can be obtained, where I is the minimum number of Boolean variables among terms in the expansion of Eq. (9.5) whose Boolean variables are equal to zero. Therefore, put x. = 1 for any i (0 < i < 2 -l), where i / \> i t i- 2 ' '"' i ^ ± £ Then, the greatest possible number of most efficient codes is (N - £) (9.10) -103- and the most efficient codes consist of the binary codes corresponding to a; (0 < i < 2 n - 1) for 1 / i,, i / i oJP ..., i / V Remark 9 ■ 1 - Without loss of generality, u € V can be assumed. Therefore, x. = 1 can be assumed, Example $.1 . The case n = 3> P = 2 From Example 3»3.> h' = 0, b. = h = h, = 1, h = h = h. = h = l " 2 "' 1* "' ' 3 5 "" 6 "' 7 can be obtained. Therefore, from Eq„ (9*2) X X 1 X X 2 x o x u X 1 X 3 X 1 X 5 X 2 X 3 X 2 X 6 X 3 X 7 x h x 5 x k x 6 X 5 X 7 = o ^ = = = = = = = = = = > (9.11) x 6 x ? = J -101+- can be obtained. From Remark 9.1, (9-12) *o = 1 holds without loss of generality. Therefore, from Eq. (9«5)> y 1 y 2 y i+ (y 1 v yJ(y x v y^)(y 2 v y 3 )(y 2 v ygKy^ v y ) • (y^ v y 5 )(y J+ v y^)(y 5 ^ y 7^ y 6 v y 7^ = 1 can be obtained. Therefore, Eq. (9 = 12) = y 1 y 2 y i ^(y 1 v y^Hyg v y 3 y 6 )(y 3 v y^)(y J+ v y^Ky y 6 v y^) = y 1 y 2 y 1+ (i v y^H 1 ^ y^)^ ^ y^)(i v y 5 y 6 )(y^y 6 v y ? ) = y 1 y 2 y i ^(y 3 v y 7 )(y 5 y 6 v y^) = y 1 y 2 y i+ (y 3 y 5 y 6 v y ? ) = y 1 y 2 y i ^y 7 v y^ 2 y y f h y 3 v G (9.13) The term of the right-hand side of Eq. (9.I3) whose number of variables is minimal is y ]_ y 2 y 4 y 7 Therefore, the greatest possible number of most efficient codes is 2 - k = h. Therefore, y 1 y 2 y i+ y ? = i can be obtained. Therefore, -105- x l_ = x 2 = \ = X Y " ° Accordingly, x " x 3 " x 5 " x 6 " 1 can be obtained. Therefore, the most efficient codes are ° 1 1 1 1 ll 1 10. CONCLUSION Most efficient codes were found in principle by the methods discussed above . Now, define m , m , m as follows: GOO m : the number of most efficient group codes G m : the number of most efficient codes under Condition 6.1 and Condition 6.2 m : the number of most efficient codes in general From the description of Section 7 and Remark 7° 3* 2 < m_ < m_ < m_ < 2 n_P+1 (10. l) G L (J can be obtained. As a future problem, do there exist most efficient codes under Condition 6„1 and Condition 6.2 such that m > m_? Another problem is to G obtain an elegant method of solution for general most efficient codes such that m o > V This paper has presented a new conclusion, that the most efficient codes problem under Condition 6.1 and Condition 6.2 including group codes has been solved completely. -106- 1/ M 2 a tm